The present application is directed to a method and apparatus for performing encryption and decryption. More particularly, the present application is directed to modular arithmetic circuits and methods, as opposed to standard arithmetic operations.
Modular arithmetic, with its implied division operations, is much more difficult to perform and to calculate, particularly where exponentiation modulo N is involved.
The multiplication of binary numbers modulo N is an important operation in modern, public-key cryptography. The security of any cryptographic system which is based upon the multiplication and subsequent factoring of large integers is directly related to the size of the numbers employed, that is, the number of bits or digits in the number. For example, each of the two multiplying factors may have a large number of hits, perhaps 1,024 bits. However, for cryptographic purposes, if is necessary to carry out this multiplication modulo a number N. Accordingly, it should be understood that the multiplication considered herein multiplies two n bit numbers to produce a result with n bits or less, rather than the usual 2n bits in conventional multiplication.
However, even though there is a desire for inclusion of a large number of bits in each factor, the speed of calculation becomes significantly slower as the number of digits or bits increase. It may be convenient to break up the modulo N multiplication of large numbers into a series of operations as to smaller pieces of each number which are handled by each of a set of processing elements arranged in a series. For example in commonly owned U.S. Pat. No. 6,804,696 describes a system and method in which operational cycles used to perform modulo N multiplication are partitioned into two phases; X and Z. Each processing element in a series of processing elements performs the X-phase of a modulo N multiplication operation, after which each processing element performs the Z-phase, then returning to the X-phase again.